Thuật toán Tìm kiếm theo chiều rộng

Hình động minh họa thuật toán tìm kiếm theo chiều rộng

Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi để lưu trữ thông tin trung gian thu được trong quá trình tìm kiếm:

  1. Chèn đỉnh gốc vào hàng đợi (đang hướng tới)
  2. Lấy ra đỉnh đầu tiên trong hàng đợi và quan sát nó
    • Nếu đỉnh này chính là đỉnh đích, dừng quá trình tìm kiếm và trả về kết quả.
    • Nếu không phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được quan sát trước đó vào hàng đợi.
  3. Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được quan sát – dừng việc tìm kiếm và trả về "không thấy".
  4. Nếu hàng đợi không rỗng thì quay về bước 2.

Ghi chú: Nếu sử dụng một ngăn xếp thay vì hàng đợi thì thuật toán trở thành thuật toán tìm kiếm theo chiều sâu.